package graph;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-20 13:17
 **/
public class LeetCode475 {

    //排序+双指针
    public int findRadius(int[] houses, int[] heaters) {
        //排序房子和取暖器
        Arrays.sort(houses);
        Arrays.sort(heaters);

        int res = 0;
        for (int i = 0, j = 0; i < houses.length; ++i) {
            int curDistance = Math.abs(houses[i] - heaters[j]);

            while (j < heaters.length - 1 && Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])) {
                ++j;
                //找到能够覆盖当前房屋最近的取暖器距离
                curDistance = Math.min(curDistance, Math.abs(houses[i] - heaters[j]));
            }

            //更新能够覆盖所有房屋的半径
            res = Math.max(res, curDistance);
        }
        return res;
    }


    //对于每个房屋，要么用前面的暖气，要么用后面的，二者取近的，得到距离
    /*public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);

        //存取可以覆盖所有的房屋的最小半径
        int res = 0;
        for (int house : houses) {
            int i = binarySearch(heaters, house);
            int j = i + 1;
            int leftDistance = i < 0 ? Integer.MAX_VALUE : house - heaters[i];
            int rightDistance = j >= heaters.length ? Integer.MAX_VALUE : heaters[j] - house;
            int min = Math.min(leftDistance, rightDistance);
            res = Math.max(res, min);
        }

        return res;
    }*/

    /*int binarySearch(int[] nums, int target) {
        //左边界
        int l = 0;
        //右边界
        int r = nums.length - 1;
        if (target < nums[l]) {
            return -1;
        }

        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return l;
    }*/

    public static void main(String[] args) {
        LeetCode475 code = new LeetCode475();
        code.findRadius(new int[]{1,2,3}, new int[]{2});
    }

}
